Batch 2 - Class 324 - Gasarch Grid Coloring

• Solve for 4 colors of chameleons in the exercise set above

• Tic tac toe
• Tic tac toe is a deterministic game - if two smart people are playing, the game will always end in a draw
• What if both players were playing with the same symbol X - who will win?
• Answer: If player 1 plays the center, then regardless of where player 2 plays, player 1 will win in next turn
• What if both players were playing with the same symbol X, but the person to create "three in a row" loses? Is there a winning strategy?
• Answer: If player 1 plays in the center, and then depending on player 2 turn, player 1 forces a hockey shape, player 1 should win

• Try for 6x6 equilateral triangle

• Try for 7x7 equilateral triangle

• In 2009, Bill Gasarch asked the question whether you could color 17x17 rectangle vertices so that there was no rectangle with vertices of same color. He then announced a prize of $289 (why!?) for anyone who solves it. A solution came by in 2012.

• The above solution does not have an upside rectangle of same color vertices, but there is a tilted ractangle (bottom row 6th from left, next 4th, next 7th, next 5th)
• Can you solve a simple Gasarch problem - can you color 5x5 square grid with 2 colors to satisfy above conditions? The following solution fails.

• If not, can you prove this doesn't have a solution?
• Answer: There have to be 13 vertices with same color on a 5x5 grid. Which means that at least 3 rows have to have 3 or more vertices of same color  (4 or 5 vertices of same color in a row can easily be ruled out because then you can't place enough on other rows without forming a rectangle). Amongst these 3 rows, show that at least two rows have to have vertices of same color in at least 2 positions, which means those form a rectangle.

• Can you think about if you were using 3 colors?
• 11x11 is the smallest grid that is guaranteed to give a monochromatic rectangle. 4 color is 19x19.
• The grid size scales to square of the number of colors

• In general, Gasarch problems fall in the NP Complete category - i.e. they are computationally very hard to solve

• Answer: There are 17 ways to spell NAH from any N, and 17 to get to an N on a HAN. Hence for each N which leads to NAH, there are 51 ways to get the initial HAN (through 3 other N's) and 17 ways to complete NAH. Hence 17x51 ways for each N. And total 4x17x51 ways, which is 3468

• (CombProbs Problem 52) Can you arrange numbers 1..9 in a circle so that sum of two neighbors is never divisible by 3, 5 or 7
• Answer: 5,6,2,9,4,7,1,3,8,(5) - One way to do this is to figure out all combinations which are "allowed", i.e. not divisible by 3,5,7. Then start to work with constraints like number 2 can only go with 6 and 9, and build from there. Number 4 can only go with 9 and 7, so that extends the sequence to 6,2,9,4,7, and so on.

• (MartinShCol - 1.6) Take a 3x3 Rubik cube. A termite starts at one of the outer cubes, and goes from one cube to next, never coming back to a cube it has been through, and never going diagonal. Is it possible for the termite to bore through each of 26 outer cubes and finish the trip at the center cube?
• Answer: No. Color alternate cubes black and white. Termite alternates between colors on the cube, and hence can not finish at the center square, which is in the 13 color set (not in the 14 color set)

• (Mathologer https://www.youtube.com/channel/UC1_uAIS3r8Vu6JjXWvastJg)

• (Dudeney - 44) Mr. and Mrs. Jorkins have fifteen children, all born at intervals of one year and a half. Miss Ada Jorkins, the eldest, had an objection to state her age to the census man, but she admitted that she was just seven times older than little Johnnie, the youngest of all. What was Ada's age? Do not too hastily assume that you have solved this little poser. You may find that you have made a bad blunder!
• Answer: 24 years (Little Johney is 3 years - its "seven times older" hence "eight times as old" - otherwise the answer would be 24.5 and 3.5)   

• (Alice - 78) The forgetful White Kinight - The White Knight told Alice about a trial where there were three defendants, and
• All three defendants knew who was guilty, and made statements to that effect
• The first defendant accused either the second or the third defendant, but the White Knight couldn't remember which one
• The second defendant claimed to be the guilty one!
• The third defendant either accused himself, or he accused the second defendant, but the White Knight couldn't remember which one
• The guilty defendant lied. Either one or both told the truth, and the White Knight couldn't remember which one

• Answer: We are given that the guilty one lied. If B were guilty, he would have told the truth when he accused himself; therefore, B cannot be guilty. If A were guilty, then all three of them would have lied (because A would have accused either B or C, both of whom were innocent; B would have accused himself, who was innocent; and C would have accused either C, who was innocent, or A, who is innocent). But we are given that not all of them lied, so A can't be guilty either. So C was guilty.

• You work for the census bureau. You call a random phone number and learn that the household has exactly two children and at least one of them is a girl. What is the probability that they are both girls? 
• Answer: 1/3
• The next day at the census bureau, you call another random phone number. This household also has exactly two children, and at least one of them is a girl who happened to be born on a Tuesday. What is the probability that they are both girls? 
• Answer: 48%
• What do you think is going on? Why did we think of 1/2 as an intuitive answer for the first problem, and then it turned out to be 1/3? Why did it get closer to 1/2 in second case? What do you think will happen if we realized that at least one of the kids is a girl who happened to be born at 12:30pm on Tuesday?

• Can you start from 3 yellow and 1 blue dot, and get the buzzer to go off?
• How many minimum moves does it take you?
• Can you start off with any position and get the buzzer to go off?
• What if you knew there were 2 blues and 2 yellow, and the ones opposite were of the same color
• Answer: You could have just flipped opposites!
• What if you knew that there were 2 blue and 2 yellow, and they were adjacent
• Answer: Flip 2 adjacent. You have either got to opposites, or the buzzer goes off. Now flip opposites!
• What if you knew there were 2 and 2, but you didn't know which ones?
• Answer: Flip opposites (if the opposites were same, buzzer goes off, else you get to 2 adjacents position). Flip Adjacent, and if the buzzer still doesn't go off, flip opposites.
• Now can you solve for 3 and 1? 
• Answer: Flip 1, and you will either get to the buzzer or a 2-and-2 position that we already know how to solve.

• Prove that product of 4 consecutive integers can not be a perfect square

• 
  
• Research about the shape of our universe

• Work out 21 x 32 using line method (https://www.youtube.com/watch?v=5ZIXdO3-fM0) by drawing 2 tens and 1 units line vertically, and 3 tens and 2 units lines horizontally. Look at intersections diagonally
• Ask kids to work out 171 x 122
• 34 x 21 (notice the carry)
• 102 x 31 (notion of zero lines)
• Why does this work?
• Show extension of the method through area method - for example, 17 x 18 as (10 + 7) x (10 + 8)
• Ask kids to work out 342 x 23
• Show correspondence with line method diagonally
• One can also think of this as (20-3)x(20-2)
• Multiplication using fingers
• Try 7 x 8 - for 7 the fist means 5 and raise two fingers on right hand to get to 7. Similarly, left hand is fist and 3 fingers up. Now each raised finger counts for 10, and then multiple the fingers that are still down. You get 56
• Let kids try 6 x 9
• Lets do 8 x 8
• Lets work with fingers and toes. 17 x 18. Use hands and toes. Now each digit up is 20, not 10 (since we have 20 digits in all)
• Why does this work? (5+a) x (5+b) = (5-a) x (5-b) + 10 (a+b) where a and b are the raised fingers.

• (Cornell) Natives Puzzle - Natives in a certain colony have a myth that there is a certain disease signaled by a blue mark on their forehead. If they find out that they have the disease, they must declare it the very next day in the townhall meeting, and leave the colony. However, no one else tells others if they have a blue mark out of courtesy. One day, a foreigner comes in, and tells the whole society that he has seen at least one blue mark in the colony. What will happen?
• We have done this problem before - now we can solve it using induction
• What happens if all the natives have a blue mark on their forehead? And why does a foreigner telling them help, since they already know the fact being stated?
• http://www.math.cornell.edu/~mec/2008-2009/ABjorndahl/ppmi.pdf
• (Cornell) Pirates Puzzle - There are 13 pirates, who find a pot of cold coins. Pirates are ranked by hierarchy. The leader must propose a distribution, and others must vote. A tie results in the proposal being passed. Otherwise, the leader/proposer is killed, and the next leader proposes a distribution. Pirates are greedy, but given all equal, they don't want to kill their fellow pirates because it makes the gang weaker. What is the final distribution?
• Solve for small number of pirates - see the pattern
• Form a hypothesis
• Base case is already proven by now
• Prove the induction step

• Team Cows and Bulls - Can do 3 rounds. Let kids choose who goes first, or by toss of coin, and play a four player Cows and Bulls. Each kid in each team goes turn by turn, and the teams get to decide the order
• Pictureka Rapid Fire - Team Game 3 minutes - One blue card will be opened at a time. Whichever team gets a card wins a point
• Tangram (Do we have two sets?)

• Were Winters Colder when Grandpa was a Child!?
• NASA has a wealth of data online, which can be used for visualization - http://mynasadata.larc.nasa.gov/lesson-plans/lesson-plans-middle-school-educators/ 
• http://mynasadata.larc.nasa.gov/lesson-plans/lesson-plans-middle-school-educators/?page_id=474?&passid=97 - Lets check temperature in Delhi for past many years to see if there has been overall warming?
• Lets do the same for Monthly Cloud Coverage and Monthly Precipitation
• What trends can you determine from your graphs of temperature, precipitation and cloud cover where you live?
• Is it an accurate statement that winters were colder in the past?
• What are some possible reasons for the changes?
• Were there notable short-term changes that may have been caused by geophysical events such as a large volcanic eruption?
• Problem 3 - India Census (Excel Sheet)
• Look at the data and draw conclusions related to following
• Which states have best and worst sex ratio?
• Which states have poorest effective literacy ratio? Which has the highest differential in female:male effective literacy ratio?
• Are Cities or Agglomerations better on sex ratio? On literacy?
• Play around for other conclusions
• Prediction on Titanic dataset 

• Pick up a problem of your interest, and search the web to find out data sources related to that. Analyze those data sources to validate or invalidate some common hypotheses.